
package com.moxi.tree;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.UnsupportedEncodingException;

/**
 * 
 * 红黑树
 * 
 * 
 * @date 2018年11月20日上午10:44:51
 */
public class RBTree {

	private RBNode mroot;
	private static final boolean RED = false;
	private static final boolean BLACK = true;

	/**
	 * 定义红黑树类
	 * 
	 * 
	 * @date 2018年11月20日上午10:16:17
	 */
	public class RBNode implements Comparable {

		private boolean color;
		private Integer key;
		private RBNode parent;
		private RBNode leftChild;
		private RBNode rightChild;
		private Integer fluctuate; // 波动值

		public RBNode(boolean col, Integer key, RBNode paret, RBNode leftChild, RBNode rightChild) {
			this.color = col;
			this.key = key;
			this.parent = parent;
			this.leftChild = leftChild;
			this.rightChild = rightChild;
			this.fluctuate = 0;
		}

		public Integer getKey() {
			return this.key;
		}

		/*
		 * (non-Javadoc)
		 * 
		 * @see java.lang.Comparable#compareTo(java.lang.Object)
		 */
		@Override
		public int compareTo(Object o) {
			int temp = this.key - (int) o;
			return temp;
		}

	}

	/**
	 * 输出父节点
	 * 
	 * 
	 * @date 2018年11月20日上午10:16:48
	 */
	public RBNode parentOf(RBNode node) {
		if (node != null) {
			return node.parent;
		}

		return null;
	}

	/**
	 * 输出节点颜色
	 * 
	 * 
	 * @date 2018年11月20日上午10:16:58
	 */
	public boolean colorOf(RBNode node) {
		if (node != null) {
			return node.color;
		}
		return BLACK;
	}

	/**
	 * 设置父节点
	 * 
	 * 
	 * @date 2018年11月20日上午10:18:28
	 */
	public void setParent(RBNode node, RBNode parent) {
		if (node != null) {
			node.parent = parent;
		}
	}

	/**
	 * 设置颜色
	 * 
	 * 
	 * @date 2018年11月20日上午10:18:40
	 */
	public void setColor(RBNode node, boolean color) {
		if (node != null) {
			node.color = color;
		}
	}

	/**
	 * 节点颜色是否红色
	 * 
	 * 
	 * @date 2018年11月20日上午10:19:00
	 */
	public boolean isRed(RBNode node) {
		return (node != null && node.color == RED) ? true : false;
	}

	/**
	 * 节点颜色是否黑色
	 * 
	 * 
	 * @date 2018年11月20日上午10:19:16
	 */
	public boolean isBlack(RBNode node) {
		return !isRed(node);
	}

	/**
	 * 设置节点颜色为红色
	 * 
	 * 
	 * @date 2018年11月20日上午10:19:36
	 */
	public void setRed(RBNode node) {
		if (node != null) {
			node.color = RED;
		}
	}

	/**
	 * 设置节点颜色为黑色
	 * 
	 * 
	 * @date 2018年11月20日上午10:19:45
	 */
	public void setBlack(RBNode node) {
		if (node != null) {

			node.color = BLACK;
		}
	}

	/**
	 * 通过Key值查找节点
	 * 
	 * 
	 * @date 2018年11月20日上午10:20:46
	 */
	public RBNode search(Integer key, RBNode node) {

		if (node != null) {

			// 比较两个节点的大小
			int com = key.compareTo(node.key);

			if (com < 0) {
				return search(key, node.leftChild);
			} else if (com > 0) {
				return search(key, node.rightChild);
			} else {
				return node;
			}
		}
		return null;

	}

	// 寻找后继节点，即大于该节点的最小节点
	public RBNode min(RBNode node) {
		if (node.leftChild == null) {
			return node;
		}

		while (node.leftChild != null) {
			node = node.leftChild;
		}

		return node;
	}

	// 寻找前驱节点，即小于该节点的最大节点
	public RBNode max(RBNode node) {
		if (node.rightChild == null) {
			return node;
		}

		while (node.rightChild != null) {
			node = node.rightChild;
		}

		return node;
	}

	/**
	 * 寻找该节点的接班人
	 * 
	 * 
	 * @date 2018年11月20日上午10:23:09
	 */
	public RBNode successor(RBNode node) {
		if (node.rightChild != null) {
			return min(node.rightChild);
		}

		RBNode y = node.parent;
		while ((y != null) && (y.rightChild == node)) {
			node = y;
			y = y.parent;
		}
		return y;
	}

	/**
	 * 左旋节点
	 * 
	 * 
	 * @date 2018年11月20日上午10:23:33
	 */
	public void leftRonate(RBNode x) {
		RBNode y = x.rightChild;

		if (y.leftChild != null) {
			y.leftChild.parent = x;
		}

		x.rightChild = y.leftChild;
		y.leftChild = x;
		y.parent = x.parent;

		if (x.parent != null) {
			if (x.parent.leftChild == x) {
				x.parent.leftChild = y;
			} else {
				x.parent.rightChild = y;
			}
		} else {
			this.mroot = y;
		}
		x.parent = y;

	}

	/**
	 * 右旋节点
	 * 
	 * 
	 * @date 2018年11月20日上午10:23:46
	 */
	public void rightRonate(RBNode x) {
		RBNode y = x.leftChild;

		if (y.rightChild != null) {
			y.rightChild.parent = x;
		}

		y.parent = x.parent;
		x.leftChild = y.rightChild;
		y.rightChild = x;

		if (x.parent != null) {
			if (x.parent.leftChild == x) {
				x.parent.leftChild = y;
			} else {
				x.parent.rightChild = y;
			}
		} else {
			this.mroot = y;
		}
		x.parent = y;
	}

	/**
	 * 添加节点修复
	 * 
	 * 
	 * @date 2018年11月20日上午10:24:00
	 */
	public void insertFixUp(RBNode node) {
		RBNode parent, gparent;
		while (((parent = parentOf(node)) != null) && isRed(parent)) {
			gparent = parentOf(parent);
			if (gparent.leftChild == parent) {
				RBNode uncle = gparent.rightChild;
				if (isRed(uncle)) {
					setBlack(parent);
					setBlack(uncle);
					setRed(gparent);

					node = gparent;
					continue;
				} else {
					if (parent.rightChild == node) {
						leftRonate(parent);
						RBNode temp = node;
						node = parent;
						parent = temp;
					}

					setBlack(parent);
					setRed(gparent);
					rightRonate(gparent);

				}
			} else {

				RBNode uncle = gparent.leftChild;
				if (isRed(uncle)) {
					setBlack(parent);
					setBlack(uncle);
					setRed(gparent);

					node = gparent;
					continue;
				} else {
					if (parent.leftChild == node) {
						rightRonate(parent);
						RBNode temp = node;
						node = parent;
						parent = temp;
					}
					setBlack(parent);
					setRed(gparent);
					leftRonate(gparent);
				}
			}
		}

		if (mroot == node) {
			setBlack(node);
		}
	}

	/**
	 * 红黑树删除修复
	 * 
	 * 
	 * @date 2018年11月20日上午10:24:22
	 */
	public void deleteFixUp(RBNode node, RBNode parent) {

		RBNode other;
		while (isBlack(node) && node != this.mroot) {

			if (parent.leftChild == node) {
				other = parent.rightChild;
				if (isRed(other)) {
					setRed(parent);
					setBlack(other);
					leftRonate(parent);
					continue;
				} else {
					if (isBlack(other.leftChild) && isBlack(other.rightChild)) {
						setRed(other);
						node = parent;
						parent = parentOf(node);

					} else if (isRed(other.leftChild) && isBlack(other.rightChild)) {
						setRed(other);
						setBlack(other.leftChild);
						rightRonate(other);
					} else if (isRed(other.rightChild)) {
						setColor(other, colorOf(parent));
						setBlack(parent);
						setBlack(other.rightChild);
						leftRonate(parent);
						break;
					}
				}
			} else {
				other = parent.leftChild;
				if (isRed(other)) {
					setBlack(other);
					setRed(parent);
					rightRonate(parent);
					continue;
				} else {
					if (isBlack(other.leftChild) && isBlack(other.rightChild)) {
						setRed(other);
						node = parent;
						parent = parentOf(node);

					} else if (isRed(other.rightChild) && isBlack(other.leftChild)) {
						setRed(parent);
						setBlack(other.rightChild);
						leftRonate(other);
					} else if (isRed(other.leftChild)) {
						setColor(other, colorOf(parent));
						setBlack(parent);
						setBlack(other.leftChild);
						rightRonate(parent);
						break;
					}
				}
			}
		}

		setBlack(node);

	}

	/**
	 * 红黑树添加
	 * 
	 * 
	 * @date 2018年11月20日上午10:24:32
	 */
	public void insert(RBNode node) {

		int com;
		RBNode x = this.mroot;
		RBNode y = null;
		Integer fluctuate = Integer.MAX_VALUE; // 初始波动值为0
		while (x != null) {

			y = x;

			com = node.key.compareTo(x.key);
			int vv = node.key - x.key;
			if (Math.abs(vv) < fluctuate) {
				fluctuate = Math.abs(vv);
			}

			if (com < 0) {
				x = x.leftChild;
			} else {
				x = x.rightChild;
			}

		}

		node.parent = y;

		node.fluctuate = fluctuate;

		if (y != null) {

			com = node.key.compareTo(y.key);

			if (com < 0) {
				y.leftChild = node;
			} else {
				y.rightChild = node;
			}
		} else {
			this.mroot = node;
		}
		setRed(node);
		insertFixUp(node);
	}

	public void insert(Integer key) {

		RBNode node = new RBNode(BLACK, key, null, null, null);

		if (node != null) {
			insert(node);
		}
	}

	/**
	 * 红黑树删除
	 * 
	 * 
	 * @date 2018年11月20日上午10:24:58
	 */
	public void delete(RBNode node) {

		RBNode child, parent, replace;
		boolean color = true;
		if (node.leftChild != null && node.rightChild != null) {
			replace = successor(node);

			parent = parentOf(replace);
			child = replace.rightChild;
			color = colorOf(replace);

			if (node == parentOf(replace)) {
				parent = replace;
			} else {
				if (child != null) {
					setParent(child, parentOf(replace));
				}
				replace.parent.leftChild = child;
				replace.rightChild = node.rightChild;
				setParent(node.rightChild, replace);
			}

			setParent(replace, parentOf(node));
			replace.leftChild = node.leftChild;
			setParent(node.leftChild, replace);
			setColor(replace, colorOf(node));

			if (parentOf(node) != null) {
				if (node.parent.leftChild == node) {
					node.parent.leftChild = replace;
				} else {
					node.parent.rightChild = replace;
				}
			} else {
				this.mroot = replace;
			}

			if (color == BLACK) {
				deleteFixUp(child, parent);
			}
		} else {

			if (node.leftChild != null) {
				replace = node.leftChild;
			} else {
				replace = node.rightChild;
			}

			parent = parentOf(node);

			if (parent != null) {
				if (parent.leftChild == node) {
					parent.leftChild = replace;
				} else {
					parent.rightChild = replace;
				}
			} else {
				this.mroot = replace;
			}
			setParent(replace, parent);

			color = colorOf(node);
			child = replace;
			if (color == BLACK) {
				deleteFixUp(child, parent);
			}
		}

	}

	public void delete(Integer key) {
		RBNode node;
		if ((node = search(key, this.mroot)) != null) {
			delete(node);
		}
	}

	/**
	 * 前序遍历
	 * 
	 * 
	 * @date 2018年11月20日上午10:25:10
	 */
	public void preOrder(RBNode node) {
		if (node != null) {
			System.out.println(node.key + " ");
			preOrder(node.leftChild);
			preOrder(node.rightChild);
		}
	}

	public void preOrder() {
		preOrder(this.mroot);
	}

	/**
	 * 中序遍历
	 * 
	 * 
	 * @date 2018年11月20日上午10:25:21
	 */
	public void inOrder(RBNode node) {
		if (node != null) {
			inOrder(node.leftChild);
			System.out.println(node.key + " ");
			inOrder(node.rightChild);
		}
	}

	public void inOrder() {
		inOrder(this.mroot);
	}

	/**
	 * 后序遍历
	 * 
	 * 
	 * @date 2018年11月20日上午10:25:29
	 */
	public void postOrder(RBNode node) {
		if (node != null) {
			postOrder(node.leftChild);
			postOrder(node.rightChild);
			System.out.println(node.key + " ");
		}
	}

	public void postOrder() {
		postOrder(this.mroot);
	}

	/**
	 * 打印红黑树
	 * 
	 * 
	 * @date 2018年11月20日上午10:25:55
	 */
	public void print(RBNode node, int direction) {
		if (node != null) {
			if (direction == 0) {
				System.out.printf("%2d(%s) is root\n", node.key, node.color == false ? "R" : "B");
			} else {
				System.out.printf("%2d(%s) is %s child 父节点 %2d\n", node.key, node.color == false ? "R" : "B",
						direction == -1 ? "left" : "right", node.parent.key);
			}
			print(node.leftChild, -1);
			print(node.rightChild, 1);
		}
	}

	public void print() {
		print(this.mroot, 0);
	}

	/**
	 * 将文件中的内容读取出来
	 * 
	 * 
	 * @date 2018年11月20日上午11:37:52
	 */
	public static String readToString(String fileName) {
		// String encoding = "UTF-8";
		String encoding = "gbk";
		File file = new File(fileName);
		Long filelength = file.length();
		byte[] filecontent = new byte[filelength.intValue()];
		try {
			FileInputStream in = new FileInputStream(file);
			in.read(filecontent);
			in.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		try {
			return new String(filecontent, encoding);
		} catch (UnsupportedEncodingException e) {
			System.err.println("The OS does not support " + encoding);
			e.printStackTrace();
			return null;
		}
	}

	/**
	 * 
	 * 
	 * @date 2018年11月20日下午8:22:34
	 */
	public static void main(String[] args) throws IOException {

		RBTree tree = new RBTree();

		int[] a = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };

		String text = readToString("D:\\testingdata.txt");

		// System.out.println(text);

		// 将文本中的回车换行替换掉
		text = text.replaceAll("[\\t\\n\\r]", "");

		String[] textList = text.split("，");

		int minSum = 0;

		// 红黑树添加测试
		for (int i = 0; i < textList.length; i++) {
			if (textList[i].trim() == null || textList[i].trim() == "") {
				return;
			}

			Integer key = Integer.valueOf(textList[i]);

			if (tree.search(key, tree.mroot) == null) {
				tree.insert(key);
			} else {
				continue;
			}

			// 第一天的时候，就是他自己
			if (i == 0) {
				minSum = minSum + key;
			} else {
				minSum += tree.search(key, tree.mroot).fluctuate;
			}

		}

		System.out.println("使用红黑树计算");

		System.out.println("得到的波动值是:" + minSum);

		if (tree.max(tree.mroot) != null) {
			System.out.println("最大值:" + tree.max(tree.mroot).key);
		}

	}

}
